package offer.offer02;

/**
 * 太强了
 */
public class Solution36_2 {
    Node36 head, pre;
    public Node36 treeToDoublyList(Node36 root) {
        if(root==null) return null;
        dfs(root);

        pre.right = head;
        head.left =pre;//进行头节点和尾节点的相互指向

        return head;

    }

    public void dfs(Node36 cur){
        if(cur==null) return;
        dfs(cur.left);
        //注意这里的head在整个程序中仅会进行一次赋值,当整个程序遇到第一个左子树为null
        //的节点时, 此时pre==null, 会把head赋值给这个cur, 这个cur必为最小值
        if(pre==null) head = cur;

        else pre.right = cur;
        //左子树 - 父节点 - 右子树, 这个遍历流程走到父节点(中间的)的时候, cur一定是最大值
        //即使右子树有更大的值, 也会在右子树遍历的时候重新设置pre;
        cur.left = pre;
        //pre总是要指向当前节点, 因为是中序遍历, 所以每次我们访问当当前节点的时候,
        //当前节点一定是我们访问过的最大的值
        pre = cur;
        dfs(cur.right);
    }
}
